package GreedyAlgorithm;

import java.util.Arrays;

/**
 * 贪心算法-会议安排问题
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/20 15:28
 */
public class MeetingArrangement {
    public static void main(String[] args) {
        int[] s = {0, 3, 1, 5, 2, 5, 3, 8, 6, 8, 12}; // 开始时间
        int[] f = {0, 6, 4, 7, 5, 9, 8, 11, 10, 12, 14};//结束时间
        int[] item = arange(s, f);
        for (int i = 1; i < item.length; i++) {
            if (item[i] == -1) break;
            System.out.print(item[i] + " ");
        }

    }

    /**
     * 结束时间早的优先
     *
     * @param s
     * @param f
     */
    static int[] arange(int[] s, int[] f) {
        if (s.length != f.length) {
            int[] item = {0, -1};
            return item;
        }
        int len = s.length;
        int[] item = new int[len];
        int[][] x = new int[len][3];
        for (int i = 1; i < len; i++) { // 初始化数据
            x[i][0] = i;
            x[i][1] = s[i];
            x[i][2] = f[i];
        }

        // 根据结束时间排序
        Arrays.sort(x, (o1, o2) -> o1[2] - o2[2]);
        item[0] = 0;
        item[1] = x[1][0];
        int n = 2, last = x[1][2];
        for (int i = 2; i < len; i++) {
            if (x[i][1] >= last) { // 开始时间小于上次会议结束时间
                item[n++] = x[i][0];
                last = x[i][2];
            }
        }
        if (n < len) item[n] = -1;
        return item;
    }

}

